package com.samxcode.leetcode;

/**
 * '?' Matches any single character. '*' Matches any sequence of characters (including the empty
 * sequence).
 * 
 * The matching should cover the entire input string (not partial).
 * 
 * The function prototype should be: bool isMatch(const char *s, const char *p)
 * 
 * Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false
 * isMatch("aa", "*") → true isMatch("aa", "a*") → true isMatch("ab", "?*") → true isMatch("aab",
 * "c*a*b") → false
 * 
 * solution:
 * 贪心法
 * p每遇到一个*，就保留住当前*的坐标和s的坐标，然后s从前往后扫描，如果不成功，则s++,重新扫描。
 * http://shmilyaw-hotmail-com.iteye.com/blog/2154716
 * 
 * @author Sam
 *
 */
public class WildcardMatching {

    public static void main(String[] args) {
        System.out.println(isMatch("", "*"));
    }


    public static boolean isMatch(String s, String p) {
        char[] ss = s.toCharArray();
        char[] ps = p.toCharArray();
        int si = 0, pi = 0, sk = 0, pk = -1;
        int sl = ss.length, pl = ps.length;
        while (si < sl) {
            if (pi < pl && (ps[pi] == ss[si] || ps[pi] == '?')) {
                si++;
                pi++;
            } else if (pi < pl && ps[pi] == '*') {
                pk = pi;
                sk = si;
                pi++;
            } else if (pk != -1) {
                pi = pk + 1;
                si = ++sk;
            } else {
                return false;
            }
        }
        while (pi < pl && ps[pi] == '*')
            pi++;
        return pi == pl;
    }
}
